package class01;

public class MyCode03_Sort {
    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    //选择排序，选出最小值位置，与i位置交换
    public static int[] selectSort(int[] arr) {
        if(arr == null || arr.length < 2 ) return arr;

        int N = arr.length;
        for (int i = 0; i < N; i++) {
            int minValueIndex = i;
            for (int j = i + 1; j < N ; j++) {
                if(arr[j] < arr[minValueIndex]){
                    minValueIndex = j;
                }
            }
            swap(arr, i, minValueIndex);
        }
        return arr;
    }

    //冒泡，相邻两个数谁大谁往后挪，一轮遍历后，最大的数在最后
    public static int[] bubbleSort(int[] arr) {
        if(arr == null || arr.length < 2 ) return arr;

//        0 ~ N-1
//        0 ~ N-2
//        0 ~ N-3
//        0 ~ end
        int N = arr.length;
        for (int end = N-1; end >= 0; end--) {
            //0 ~ N 干一堆事情
            //0 1   1 2   2 3   end-1 end 相邻两个谁大谁往后
            for (int second = 1; second <= end; second++) {
                if(arr[second-1] > arr[second]){
                    swap(arr, second, second -1);
                }
            }
        }
        return arr;
    }

    //插入排序，从第二个位置开始，每次与上一个数比较，当前小于上一个位置的情况交换
//    0-0 做到有序
//    0-1 做到有序
//    ……
//    0-N 做到有序
    public static int[] insertSort(int[] arr) {
        if(arr == null || arr.length < 2 ) return arr;

        int N = arr.length;
        for (int i = 1; i < N; i++) {
            for (int j = i; j > 0; j--) {
                if(arr[j] < arr[j-1]){
                    swap(arr, j, j-1);
                }
            }
        }
        return arr;
    }
    public static void main(String[] args) {
        int[] arr = {9,2,4,3,8,5,7,1,6};
        int N = arr.length;
        for (int i = 0; i < N; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();

//        System.out.println("选择排序后");
//        arr = selectSort(arr);
//        for (int i = 0; i < N; i++) {
//            System.out.print(arr[i] + " ");
//        }

        System.out.println("冒泡排序后");
        arr = bubbleSort(arr);
        for (int i = 0; i < N; i++) {
            System.out.print(arr[i] + " ");
        }

//        System.out.println("插入排序后");
//        arr = insertSort(arr);
//        for (int i = 0; i < N; i++) {
//            System.out.print(arr[i] + " ");
//        }

        System.out.println();
    }

    public static int[] generateRandomArray(int maxSize, int maxValue) {
        // Math.random() [0,1)
        // Math.random() * N [0,N)
        // (int)(Math.random() * N) [0, N-1]
        int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
        for (int i = 0; i < arr.length; i++) {
            // [-? , +?]
            arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
        }
        return arr;
    }

    public static int[] copyArray(int[] arr) {
        if (arr == null) {
            return null;
        }
        int[] res = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            res[i] = arr[i];
        }
        return res;
    }
}
